package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。


示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]
 */
class leetcode_17 {
    @Test
    fun test_1() {
        val actual = letterCombinations("23")
        val expect = arrayListOf("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf")
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = letterCombinations("")
        val expect: ArrayList<String> = arrayListOf()
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = letterCombinations("2")
        val expect: ArrayList<String> = arrayListOf("a", "b", "c")
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    fun letterCombinations(digits: String): List<String> {
        /*
        回溯法
        注意：
        1 数字的长度 - 决定树的纵向深度
        2 数字的字符长度 - 决定树的横向宽度
         */
        backtrcaking(digits.toCharArray(), 0)
        return result
    }

    var path: String = ""
    val result: ArrayList<String> = ArrayList<String>()

    // TODO: arrayOf
    val map: Array<CharArray> = arrayOf(
        // 0
        charArrayOf()
        // 1
        , charArrayOf()
        // 2
        , charArrayOf('a', 'b', 'c')
        // 3
        , charArrayOf('d', 'e', 'f')
        // 4
        , charArrayOf('g', 'h', 'i')
        // 5
        , charArrayOf('j', 'k', 'l')
        // 6
        , charArrayOf('m', 'n', 'o')
        // 7
        , charArrayOf('p', 'q', 'r', 's')
        // 8
        , charArrayOf('t', 'u', 'v')
        // 9
        , charArrayOf('w', 'x', 'y', 'z')
    )

    private fun backtrcaking(digits: CharArray, index: Int) { // index - 数字index
        // 终止条件
        // TODO:注意这种例外情况
        if (digits.isEmpty()) {
            return
        }
        // 2 收集结果： path size == 数字 size
        // 树深：数字的长度
        if (path.length == digits.size) {
            result.add(path)
            return
        }
        // println("index=$index")
        // println("digits[index]=${digits[index]}")
        // 数字 ->  字母
        val num: Int = digits[index] - '0'
        // println("num=$num")
        val chars: CharArray = map[num]

        // 3 单层循环
        for (i in 0..chars.size - 1) { // [0, 字母 end index]
            // 树层：字母长度
            // 4 处理节点
            path = path + chars[i]
            // println("for [0] : path=${path}")
            // 5 递归
            backtrcaking(digits, index + 1)
            // 6 回溯
            // TODO : substring
            path = path.substring(0 until path.length - 1) // 删除最后一个字母 [0, end index)
            // println("for [1] : path=${path}")
        }
    }
}